COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00006 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A67.tex[254,mps]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, October 1988}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Examples of Machine Simulations}
\smallskip
On unsigned counter machine $M↑\prime = \langle {\tt control}, {\tt counter}
\rangle$, with the minimum repertory of counter operations {\tt incr}, {\tt decr},
{\tt zero}, program $P↑\prime$ simulates program $P$ on machine $M$ having a
larger repertory.  The representation relation $\rho$ is the identity.

{\tt nonzero}:
\vskip 1.5in
{\tt diminish}:
\vskip 1.5in
On stack machine $M↑\prime = \langle {\tt control}, {\tt stack}, {\tt input}
\rangle$, with minimal repertory of stack operations, {\tt push}, {\tt pop},
program $P↑\prime$ simulates program $P$ on machine $M$, having a larger
repertory.  Here, \# is a symbol not in stack alphabet for $P$.  The representation
relation is $\langle \gamma↓Q, \rho↓{\Sigma↑*}, \gamma↓{\Sigma↑*}\rangle$ where
$\rho↓\Sigma = \gamma↓{\Sigma↑*-\{\Lambda\}} \cup \{\langle \#,\Lambda \rangle\}$.
\medskip
{\tt Initialization}:
\vskip 2in
\vfill\eject
For all $a\in\Sigma$, we have

{\tt push} a:
\vskip 1in
{\tt pop} a:
\vskip 1in
{\tt empty}
\vskip 1in
Furthermore, we can require the simulating machine $M↑\prime$ to have $\Lambda$
as its stack's only accepting state. Here, we've substituted an output 
device for the input device.
\vskip 2in
\noindent{\bf Buffering}

Operations to test stack or input include {\tt pop a} and {\tt scan a}, which
are destructive.  A machine without nondestructive operations {\tt top},
{\tt next}, can simulate them with the aid of a finite store called a
{\tt buffer}.  We illustrate for input; the details for stacks are left as an
exercise.  The buffer, {\tt buf} has carrier $\Sigma \cup \{e, \Lambda\}$,
where $e \in \Sigma$.  If {\tt buf} is not $e$, {\tt buf} $\otimes$
${\tt input}↓{M↑\prime}$ represents ${\tt input}↓M$.  The case ${\tt buf} = e$
represents ${\tt input}↓M = \Lambda$.  Let $M = \langle{\tt control},
{\tt input}↓n\rangle$, $M↑\prime = \langle {\tt control}, {\tt buf},
{\tt input}↓{M↑\prime}\rangle$.
\vfill\eject
For all $a \in \Sigma$:
\vskip 6in
Notice:  All input is now done by {\tt scan}s, and after an {\tt eof}, the
buffer contents remain $e$, and no more input operations are done.
\end